0930. 和相同的二元子数组【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 前缀和 + 哈希表

1. 📝 题目描述

• leetcode

给你一个二元数组 nums，和一个整数 goal，请你统计并返回有多少个和为 goal 的 非空 子数组。

子数组 是数组的一段连续部分。

---

示例 1：

输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]

示例 2：

输入：nums = [0,0,0,0,0], goal = 0
输出：15

---

提示：

• 1 <= nums.length <= 3 * 10^4
• nums[i] 不是 0 就是 1
• 0 <= goal <= nums.length

2. 🎯 s.1 - 前缀和 + 哈希表

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} nums
 * @param {number} goal
 * @return {number}
 */
var numSubarraysWithSum = function (nums, goal) {
  const map = new Map()
  map.set(0, 1)
  let prefixSum = 0
  let count = 0

  for (const num of nums) {
    prefixSum += num
    count += map.get(prefixSum - goal) || 0
    map.set(prefixSum, (map.get(prefixSum) || 0) + 1)
  }

  return count
}

• 时间复杂度：$O(n)$，其中 n 是数组长度
• 空间复杂度：$O(n)$，哈希表存储前缀和计数

算法思路：

• 维护前缀和 prefixSum 和一个哈希表记录每个前缀和出现的次数
• 初始化令前缀和 0 出现 1 次（处理从下标 0 开始的子数组）
• 遍历数组，对每个位置查找 prefixSum - goal 在哈希表中出现的次数，累加到结果中